#include <iostream>
#include <vector>

using namespace std;

// 形成大根堆-solution1
void Bigheap(std::vector<int>&arr){
    if (arr.size() <= 1) return;
    for(int i=0;i<arr.size();++i){
        heapInsert(arr,i);
    }
}

//插入操作：一个个的插入元素，时间复杂度是log（N）；总的复杂度是O（NlogN）
void heapInsert(std::vector<int>& arr,int index) {
    while(arr[index] > arr[(index-1)/2]) {
        std::swap(arr[index],arr[(index-1)/2]);
        index = (index-1)/2;
    }
}

// 堆排序-solution2
void heapify(std::vector<int>& arr,int index,int heapSize){
    int left = index*2 +1;
    while(left<heapSize){
        int largest = left+1 < heapSize && arr[left+1]>arr[left]?
            left+1 :left;
        largest = arr[largest] > arr[index]?largest:index;
        if(largest == index){
            break;
        }
        std::swap(arr[largest],arr[index]);
        index = largest;
        left = index*2 +1;
    }
}

void heapSort(std::vector<int>& arr){
    if(arr.size()<2) return;
    for(int i = arr.size()-1;i>=0;i--){
        heapify(arr,i,arr.size());
    }
    int heapSize = arr.size();
    std::swap(arr[0],arr[--heapSize]);
    while(heapSize>0){
        heapify(arr,0,heapSize);
        std::swap(arr[0],arr[--heapSize]);
    }
}